#include "linearList.h"

//顺序表打印
void sequenceList::print()
{
    cout << curNumberOfItem << ":";

    for(int i = 0; i < curNumberOfItem-1; i++)
    {
        cout << myList[i] << ",";
    }

    cout << myList[curNumberOfItem-1] << endl;
}



//链表打印
void linkList::print()
{
    curNode = firstNode;

    cout << listSize << ":";

    while(curNode != lastNode)
    {
        if(curNode->next == lastNode)
            cout << curNode->next->data << endl;
        else
        {
            cout << curNode->next->data << ",";
        }
        
        
        curNode = curNode->next;
    }
}
// ========== 顺序表实现 ==========
sequenceList::sequenceList(const int& capacity, const int& length, float arr[])
    : maxCapcity(capacity), curNumberOfItem(length) {
    myList = new float[maxCapcity];
    for (int i = 0; i < length; i++) {
        myList[i] = arr[i];
    }
}

sequenceList::~sequenceList() {
    delete[] myList;
}

bool sequenceList::addItem(const float& val) {
    if (curNumberOfItem >= maxCapcity) return false;
    myList[curNumberOfItem++] = val;
    return true;
}

bool sequenceList::insertItem(const int& index, const float& val) {
    if (index < 0 || index > curNumberOfItem || curNumberOfItem >= maxCapcity) return false;
    for (int i = curNumberOfItem; i > index; i--) {
        myList[i] = myList[i - 1];
    }
    myList[index] = val;
    curNumberOfItem++;
    return true;
}

int sequenceList::deleteItem(const float& val) {
    for (int i = 0; i < curNumberOfItem; i++) {
        if (myList[i] == val) {
            for (int j = i; j < curNumberOfItem - 1; j++) {
                myList[j] = myList[j + 1];
            }
            curNumberOfItem--;
            return i;
        }
    }
    return -1;
}

bool sequenceList::locate(const int& index, float& val) {
    if (index < 0 || index >= curNumberOfItem) return false;
    val = myList[index];
    return true;
}

int sequenceList::locate(const float& val) {
    for (int i = 0; i < curNumberOfItem; i++) {
        if (myList[i] == val) return i;
    }
    return -1;
}

void sequenceList::reverse() {
    for (int i = 0; i < curNumberOfItem / 2; i++) {
        float temp = myList[i];
        myList[i] = myList[curNumberOfItem - 1 - i];
        myList[curNumberOfItem - 1 - i] = temp;
    }
}

// ========== 链表实现 ==========
linkList::linkList() : firstNode(new listNode()), curNode(firstNode), lastNode(firstNode), listSize(0) {}

linkList::linkList(const int& length, float arr[]) : firstNode(new listNode()), listSize(0) {
    lastNode = firstNode;
    for (int i = 0; i < length; i++) {
        lastNode->next = new listNode(arr[i]);
        lastNode = lastNode->next;
        listSize++;
    }
}

linkList::~linkList() {
    listNode* p = firstNode;
    while (p != nullptr) {
        listNode* temp = p;
        p = p->next;
        delete temp;
    }
}

bool linkList::headInsertItem(const float& val) {
    listNode* newNode = new listNode(val, firstNode->next);
    firstNode->next = newNode;
    if (lastNode == firstNode) lastNode = newNode;
    listSize++;
    return true;
}

bool linkList::tailInsertItem(const float& val) {
    listNode* newNode = new listNode(val);
    lastNode->next = newNode;
    lastNode = newNode;
    listSize++;
    return true;
}

int linkList::insertItem(const int& index, const float& val) {
    if (index < 0 || index > listSize) return -1;
    listNode* p = firstNode;
    for (int i = 0; i < index; i++) {
        p = p->next;
    }
    listNode* newNode = new listNode(val, p->next);
    p->next = newNode;
    if (p == lastNode) lastNode = newNode;
    listSize++;
    return index;
}

int linkList::deleteItem(const float& val) {
    listNode* p = firstNode;
    while (p->next != nullptr) {
        if (p->next->data == val) {
            listNode* temp = p->next;
            p->next = temp->next;
            if (temp == lastNode) lastNode = p;
            delete temp;
            listSize--;
            return 1; 
        }
        p = p->next;
    }
    return -1;
}

bool linkList::locate(const int& index, float& val) {
    if (index < 0 || index >= listSize) return false;
    listNode* p = firstNode->next;
    for (int i = 0; i < index; i++) {
        p = p->next;
    }
    val = p->data;
    return true;
}

int linkList::locate(const float& val) {
    listNode* p = firstNode->next;
    int index = 0;
    while (p != nullptr) {
        if (p->data == val) return index;
        p = p->next;
        index++;
    }
    return -1;
}

void linkList::ascendingOrder() {
    if (listSize <= 1) return;
    for (int i = 0; i < listSize - 1; i++) {
        listNode* p = firstNode->next;
        for (int j = 0; j < listSize - i - 1; j++) {
            if (p->data > p->next->data) {
                float temp = p->data;
                p->data = p->next->data;
                p->next->data = temp;
            }
            p = p->next;
        }
    }
}

void linkList::reverse() {
    if (firstNode == nullptr || firstNode->next == nullptr) // 空链表或仅头节点时无需处理
        return;

    listNode* prev = firstNode;    // 头节点作为起始点
    listNode* curr = prev->next;   // 第一个数据节点
    listNode* next = nullptr;

    prev->next = nullptr; // 断开头节点与第一个数据节点的连接

    while (curr != nullptr) {
        next = curr->next;
        curr->next = prev; // 反转当前节点的指针
        prev = curr;       // 移动prev到当前节点
        curr = next;       // 移动curr到下一个节点
    }

    firstNode->next = prev; // 头节点指向新的尾节点（反转后的最后一个节点）
}

// ========== 合并两个链表 ==========
